#include <stdio.h>
#include <stdlib.h>

/*
	1.查找树的创建（createTree）

		假设有如下数组4,1,45,78,345,23,12,3,6,21

		首先选定4为root，然后遍历剩下的数字，如果大于等于4则放到4的右侧，小于4放到4的左侧，最后构建成的树：所有的左孩子都小于父节点，
		所有的右孩子都大于等于父节点。

												4
								1								45
									3						23		78
														12				345
													6		21

	2.遍历查找树（displayTree）
	
		按照左中右的顺序遍历树，结果为：1,3,4,5,12,21,23,45,78,345，遍历的结果就是已经排好序的数字。

	3.查找树中的节点（searchTree）

		从根节点开始，如果大于等于根节点，则查找根节点的右侧；如果小于根节点，则查找根节点的左侧，直到查找到节点。

		比如要查找12：
			比4大，往右走；
			比45小，往左走；
			比23小，往左走；
			找到12

*/

#define max_size 10

struct tree
{
  int value;
  struct tree * left;
  struct tree * right;
};

void display(int array[], int size) 
{
  int i;

  printf("The array is: ");
  for (i = 0; i < max_size; i++) 
    printf(" %d ", array[i]);
  printf("\n");
}

void display_tree(struct tree * tree)
{
  if (tree == NULL)
    return ;

  if (tree->left != NULL)
    display_tree(tree->left);

  printf(" %d ", tree->value);

    if (tree->right != NULL)
      display_tree(tree->right);
}

struct tree * search(struct tree * root, int value)
{
  if (root->value == value)
    return root;
  else if (root->value > value) {
    if (root->left != NULL)
      return search(root->left, value);
    else
      return NULL;
  }
  else {
    if (root->right != NULL)
      return search(root->right, value);
    else
      return NULL;
  }
}

/* 查找以node为节点的树中上是否存在vlaue的节点,parent为查找到的节点的父节点。  
   dir为1表示parent节点的左节点为查找结果  
   dir为2表示parent节点的右节点为查找结果 */
struct tree * search_with_parent(struct tree * root, struct tree ** parent, int * dir, int value)
{
  if (root->value == value)
    return root;
  else if (root->value > value) {
    if (root->left != NULL) {
      *dir = 1;
      *parent = root;
      return search_with_parent(root->left, parent, dir, value);
    }
    else
      return NULL;
  }
  else {
    if (root->right != NULL) {
      *dir = 2;
      *parent = root;
      return search_with_parent(root->right, parent, dir, value);
    }
    else
      return NULL;
  }
}

void insert(struct tree * root, struct tree * node) 
{
  if (node->value >= root->value && root->right != NULL) {
    insert(root->right, node);
    return;
  }

  if (node->value < root->value && root->left != NULL) {
    insert(root->left, node);
    return;
  }

  if (node->value >= root->value && root->right == NULL)
    root->right = node;

  if (node->value < root->value && root->left == NULL)
    root->left = node;
}

void delete_node(struct tree ** root, int value)
{
  struct tree * parent = NULL, * des;
  int dir = -1;
  
  des = search_with_parent(*root, &parent, &dir, value);
  if (des == NULL)
    printf("node not found.\n");
  else {
    /*
      a.要删除的node没有左右孩子，有父节点。
      如果要删除的node为父节点的左孩子，则将父节点的左孩子指针设置为NULL；
      如果要删除的node为父节点的右孩子，则将父节点的右孩子指针设置为NULL。
      最后删除node。
    */
    if (des->left == NULL && des->right == NULL) {
      if (parent != NULL) {
	if (dir == 1)
	  parent->left = NULL;
	else
	  parent->right = NULL;
      }
      else
	*root = NULL; /* b.要删除的node没有左右孩子，没有父节点（即根节点）。根节点设为NULL，删除node */
    }
	/*
	 c.要删除的node有左孩子没右孩子，有父节点
	   如果要删除的node为父节点的左孩子，则将父节点的左孩子设置为要被删除node的左孩子；
           如果要删除的node为父节点的右孩子，则将父节点的右孩子指针设置为要被删除node的左孩子。
	   最后删除node。
	 */
    else if (des->left != NULL && des->right == NULL) {
      if (parent != NULL) {
	if (dir == 1)
	  parent->left = des->left;
	else
	  parent->right = des->left;
      }
      else
	*root = des->left;	/* d.要被删除的node有左孩子没有右孩子，没有父节点。将要被删除的node的左孩子设置为根节点，删除node */
    }
	/*
	 e.要删除的node有右孩子没左孩子，有父节点
	   如果要删除的node为父节点的左孩子，则将父节点的左孩子设置为要被删除node的右孩子；
	   如果要删除的node为父节点的右孩子，则将父节点的右孩子指针设置为要被删除node的右孩子。
	   最后删除node。
	 */
    else if (des->left == NULL && des->right != NULL) {
      if (parent != NULL) {
	if (dir == 1)
	  parent->left = des->right;
	else
	  parent->right = des->right;
      }
      else
	*root = des->right; /* f.要被删除的node有右孩子没有左孩子，没有父节点。 将要被删除的node的右孩子设置为根节点，删除node */
    }
    else {
      insert(des->left, des->right);
      
      /* 
	 g.要被删除的node左右孩子都有，有父节点
	 将要被删除node的右孩子插入到左孩子中去。
	 如果要删除的node为父节点的左孩子，则将父节点的左孩子设置为要被删除node的左孩子；
	 如果要删除的node为父节点的右孩子，则将父节点的右孩子指针设置为要被删除node的左孩子。
	 最后删除node。
       */
      if (parent != NULL) {
	if (dir == 1)
	  parent->left = des->left;
	else
	  parent->right = des->left;
      }
      else
	/* 
	   h.要被删除的node左右孩子都有，无父节点
	   将要被删除node的右孩子插入到左孩子中去，父节点修改为要被删除node的左孩子，删除node节点。
	*/
	*root = des->left;
    }

    free(des);
    des = NULL;
  }
}

void create(struct tree ** root, int array[], int size)
{
  int i;
  struct tree * child;

  *root = (struct tree *) malloc (sizeof(struct tree));
  (*root)->value = array[0];
  (*root)->left = NULL;
  (*root)->right = NULL;

  for (i = 1; i < max_size; i++) {
    child = (struct tree *) malloc (sizeof(struct tree));
    child->value = array[i];
    child->left = NULL;
    child->right = NULL;
    insert(*root, child);
  }
}

void delete_tree(struct tree * node)
{
  if (node == NULL)
    return;
  
  if (node->left != NULL)
    delete_tree(node->left);

  if (node->right != NULL)
    delete_tree(node->right);

  if (node->left == NULL && node->right == NULL) {
    free(node);
    node = NULL;
  }
}

int main(int argc, char *argv[])
{
  int array[max_size] = {4, 1, 45, 78, 345, 23, 12, 3, 6, 21};
  struct tree * root, * parent;
  int value, dir;

  if (argc < 2) {
    printf("usge %s [argc:value] \n", argv[0]);
    exit(0);
  }

  display(array, max_size);
  root = NULL;
  create(&root, array, max_size);
  
  printf("the tree is(left->middle->right) : \n");
  display_tree(root);
  printf("\n");

  parent = NULL;
  value = atoi(argv[1]);
  dir = -1;

 
  printf("search value %d :", value);
  if (search(root, value) != NULL)
    printf("exist\n");
  else
    printf("not exist.\n");

  printf("delete value : %d\n", value);
  delete_node(&root, value);
  printf("\n");

  printf("the tree is (left->middle->right) : \n");
  display_tree(root);
  printf("\n");

  delete_tree(root);
  
  return 0;
}



